Project Selection Problem

FROM - Operations Research: Applications and Algorithms 4th Edition, p80, Wayne L. Winston

Star Oil Company is considering five different investment opportunities. The cash outflows and net present values (in millions of dollars) are given in Table. Star Oil has $40 million available for investment now (time 0); it estimates that one year from now (time 1) $20 million will be available for investment. Star Oil may purchase any fraction of each investment. In this case, the cash outflows and NPV are adjusted accordingly. For example, if Star Oil purchases one-fifth of investment 3, then a cash outflow of 𝟏/𝟓 (𝟓)=$𝟏 million would be required at time 0, and a cash outflow of 𝟏/𝟓 (𝟓)=$𝟏 million would be required at time 1. The one-fifth share of investment 3 would yield an NPV of 𝟏/𝟓 (𝟏𝟔)=$𝟑.𝟐 million. Star Oil wants to maximize the NPV that can be obtained by investing in investments 1–5. Formulate an LP that will help achieve this goal. Assume that any funds left over at time 0 cannot be used at time 1.

	1	2	3	4	5
Time 0 Cash outflow	11	53	5	5	29
Time 1 Cash outflow	3	6	5	1	34
NPV	13	16	16	14	39



In [1]:

    
from gurobipy import *

investments_targets = ["i1", "i2", "i3", "i4", "i5"]
expected_npv = [13,16,16,14,39]

cash_outflow = [
                [11,53,5,5,29],
                [3,6,5,1,34]
            ]

cash_budget = [40,20]

# Model
m = Model("project_selection")

invesestment_assignment = []
for i in range(len(investments_targets)):
    invesestment_assignment.append(
        m.addVar(
            vtype=GRB.CONTINUOUS,
            obj = expected_npv[i],
            name="(%s)" % (investments_targets[i])))

m.modelSense = GRB.MAXIMIZE
m.update()

for time in range(len(cash_outflow)):
    m.addConstr(
        quicksum(cash_outflow[time][c] * invesestment_assignment[c]
                 for c in range(len(investments_targets))) <= cash_budget[time], 
        "day requirment %s" % investments_targets[time])

for index in range(len(investments_targets)):
    m.addConstr(
        invesestment_assignment[index] <= 1, "varaible %s" % investments_targets[index])

    

m.optimize()

for v in m.getVars():
    print (v.varName, v.x)
    
print (m.getObjective().getValue())









    



Optimize a model with 7 rows, 5 columns and 15 nonzeros
Coefficient statistics:
  Matrix range     [1e+00, 5e+01]
  Objective range  [1e+01, 4e+01]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e+00, 4e+01]
Presolve removed 5 rows and 0 columns
Presolve time: 0.01s
Presolved: 2 rows, 5 columns, 10 nonzeros

Iteration    Objective       Primal Inf.    Dual Inf.      Time
       0    7.8106665e+01   8.092299e-01   0.000000e+00      0s
       2    5.7449017e+01   0.000000e+00   0.000000e+00      0s

Solved in 2 iterations and 0.03 seconds
Optimal objective  5.744901720e+01
(i1) 1.0
(i2) 0.20085995085995084
(i3) 1.0
(i4) 1.0
(i5) 0.2880835380835381
57.449017199017206



In [ ]: